public class Hanoi {
    public static void main(String[] args) {
        hanoi(1,'A','B','C');
        System.out.println();
        hanoi(2,'A','B','C');
        System.out.println();
        hanoi(3,'A','B','C');
        System.out.println();
        hanoi(4,'A','B','C');
    }
    public static void hanoi(int n, char A, char B, char C) {
        /*
        A,B,C分别为三根柱子，A是初始柱子，B是中间柱子，C是最终柱子
        1、当n只有1个的时候直接将它移到目标柱子C上
        2、当n大于1时，先将前n-1块圆盘借助C移动到B上
            此时的前n-1块圆盘继续递归，会先将前n-2块圆盘借助B移动到C上，
            将第n-1块圆盘移动到B上
            再将前n-2块圆盘从C借助A移动到B上，完成第二步
            注意：这里的B,C在不断换位置，意味着目标和辅助柱子在不断变化
        3、再将最大的圆盘(第n块圆盘）从A移动到C上
        4、将此时的n - 1块圆盘借助A移动到C上
         */
        if (n == 1) {
            System.out.println("Move 1 from " + A + " to " + C);
            return;
        }
        hanoi(n - 1, A, C ,B);
        System.out.println("Move " + n + " from  " + A + " to " + C);
        hanoi(n - 1, B, A, C);
    }
}
